package 代码记录.指定公司代码练习记录.腾讯云智.算法21年;

/**
 * @author zx
 * @create 2023-03-20 22:41
 */
public class 求质数 {
    /**
     * @ 埃筛法
     * 埃筛法是能够快速筛选出质数的方法之一,在众多质数筛选方法中,埃筛法虽然不是最快的方法,
     * 但绝对是最容易理解的方法。
     * 原理：从小到大开始筛选质数,当某个数被认定为质数时,那么后面能够被该数整除的数就一定不是质数,为这些数增加一个标记,
     * 当遍历到这些被标记的数时,直接跳过即可,无需再为其执行检验是否为质数的操作,因为判断一个数是否为质数是筛选质数过程中
     * 最耗时的操作,而埃筛法则能大幅度的减少该操作的执行频率,从而提高素数筛选的效率。
     */
    //求n下有多少个质数
    public static void prime(int n) {
        boolean[] flag = new boolean[n + 1];
        for(int i = 2; i <= n; i++) {
            if(flag[i]){
                continue;
            }
            System.out.print(i + "  ");
            for(int j = i; i * j <= n; j++) {
                flag[i * j] = true;
            }
        }
    }
    private static boolean isPrime(int n){
        int i = 2;
        for(i = 2;i <= Math.sqrt(n);i++){
            //只要模一次是0,就不是素数
            if(n % i == 0){
                return false;
            }
        }
        return i > Math.sqrt(n);//是素数
    }
}
